記錄學習內容。看網路上大大們的文章和影片，做些紀錄。
以下內容大多來自網路上大大們的文章。
還不了解，內容可能有錯誤。

之前有紀錄排序的程式 ，現在學習排序的一些觀念

java，Bubble sort algorithm 和c++， Insertion Sort 、Selection Sort
https://ithelp.ithome.com.tw/articles/10214653

主要是看
[演算法] 排序演算法(Sort Algorithm)
http://notepad.yehyeh.net/Content/Algorithm/Sort/Sort.php

氣泡排序法(Bubble Sort)

best時間複雜度: Ο(n)

因為 如果 數列是1 2 3 4 5， 第一次執行Bubble Sort時，沒有任何交換，就會跳出迴圈。所以只跑一次陣列長度，所以是Ο(n) 。

worst時間複雜度: Ο(n * n)

如果資料是 5 4 3 2 1。
第1次	跑程式 -- > 把5 推到最後面 -- > 4 3 2 1 5  (執行4次)
第2次	跑程式 -- > 把4 推到最後面 -- > 3 2 1 4 5(執行3次)
第3次	跑程式 -- >  把3 推到最後面 -- > 2 1 3 4 5(執行2次)
第4次	跑程式 -- >  把2 推到最後面 -- > 1 2 3 4 5(執行1次)
總共10次 。(n-1)+ ………….+1 ，就是 n* (n-1) /2  ，所以時間複雜度是Ο(n * n)

avg時間複雜度: Ο(n * n)

每個數字執行次數是4、3、2、1

所以平均每個數字的執行次數 就是  (4+3+2+1) /4

每個數字的執行次數 -- >(n-1)+(n-2).../4

有 n 個數字

相乘  n  *  (n-1)+(n-2).../4 

還是看到n*n ，所以時間複雜度是Ο(n * n)

空間複雜度(Space Complexity)：θ(1)

因為 不需要 額外的陣列去存資料 ，也沒有遞迴

穩定性(Stable/Unstable)：穩定(Stable)

像是 : 8 3 8

Insertion Sort

Best Case：Ο(n)

如果原本資料是 1 2 3 4 5 ，因為後面每一項都比前一項大，所以只會走一次迴圈 。

Worst Case：Ο( n * n)

如果原本資料是 5 4 3 2 1 
第一次執行: 4 5 3 2 1  -- >1次
第二次執行: 3 4 5 2 1   -- >2次
第三次執行: 2 3 4 5 1   -- >3次
第四次執行: 1 2 3 4 5 -- >4次
總共10次 。(n-1)+ ………….+1 ，就是 n * (n-1)  / 2   ，所以時間複雜度是Ο(n2)

Average Case：Ο( n * n)

Comparison Sort: Insertion Sort(插入排序法)
http://alrightchiu.github.io/SecondRound/comparison-sort-insertion-sortcha-ru-pai-xu-fa.html

平均的證明好像很麻煩，文章最後有給連結。

(方便記憶，還是先這樣想，應該是錯的)
每個數字執行次數是1、2、3、4

所以平均每個數字的執行次數 就是  (1+2+3+4) /4

每個數字的執行次數 -- >(n-1)+(n-2).../4

有 n 個數字

相乘  n  *  (n-1)+(n-2).../4 

還是看到n*n ，所以時間複雜度是Ο(n * n)

空間複雜度(Space Complexity)：θ(1)

穩定性(Stable/Unstable)：穩定(Stable)

Selection Sort

Best Case：Ο( n * n)

因為每一輪 都要去找 最小索引(陣列的索引) 。 
每一輪要結束前 在檢查 最小索引 是不是 有改變 。
有改變 就交換值 。
好像沒辦法提早結束 ， 所以兩層迴圈 ，就要n平方
但是交換次數可以是O(0) ，因為1 2 3 4 5 ，不用交換 。

Worst Case：Ο( n * n)

交換次數是O(n)  ， 因為每一輪，頂多交換一次 。
所以 5 4 3 2 1  ， 只要交換4次

5 4 3 2 1  ， 在氣泡排序法 ，要交換幾次 ?
4 + 3 + 2 +1 次 等於10次 。

Average Case：Ο( n * n)

空間複雜度(Space Complexity)：θ(1)

穩定性(Stable/Unstable)：不穩定(Unstable)

因為

但是文章有講Selection Sort 可以是stable的:

參考:
Stable Selection Sort
https://www.geeksforgeeks.org/stable-selection-sort/

因為可以不用交換的方式:

所以程式改成這樣:

每一輪 ，選到最小索引值後。
把 i 索引 和 最小值索引 之間的元素， 往右移動一格
之後 ，最小索引的值 蓋掉 i索引的值

選擇排序法(Selection Sort)
https://emn178.pixnet.net/blog/post/93915544-%E9%81%B8%E6%93%87%E6%8E%92%E5%BA%8F%E6%B3%95(selection-sort)

文章還有講到 用額外空間 的方式

原本的數列(unsort) -- >未排序 -- > unsorted
後來的數列 (sort) -- >排序 -- > sorted

每一輪 去找原本數列 (unsort) 的最小索引 ，然後刪掉 原本數列 (unsort)的最小索引 元素 ，
把元素放到 後來的數列(sort)